لماذا يتم معالجة مصفوفة تم فرزها بشكل أسرع من معالجة مصفوفة لم يتم فرزها؟

أنت ضحية فشل توقع فرع.
ما هو توقع الفرع؟
ضع في اعتبارك تقاطع سكة ​​حديد:
الصورة بواسطة Mecanismo ، عبر ويكيميديا ​​كومنز. تُستخدم بموجب ترخيص CC-By-SA 3.0.
الآن من أجل الجدل ، افترض أن هذا يعود إلى القرن التاسع عشر - قبل الاتصال عن بعد أو الاتصال اللاسلكي.
أنت عامل تقاطع وتسمع قطارًا قادمًا. ليس لديك فكرة عن الطريق الذي من المفترض أن يسلكه. توقف القطار لتسأل السائق عن الاتجاه الذي يريده. ثم تقوم بتعيين المفتاح بشكل مناسب.
القطارات ثقيلة ولديها الكثير من الجمود. لذلك يستغرقون وقتًا طويلاً لبدء التشغيل والإبطاء.
هل هناك طريقة أفضل؟ تخمن في أي اتجاه سيذهب القطار!
إذا خمنت بشكل صحيح ، فستستمر.
إذا خمنت بشكل خاطئ ، فسيتوقف القبطان ، ويعود ويصرخ عليك لقلب المفتاح. ثم يمكن إعادة تشغيل المسار الآخر.
إذا كنت تخمن بشكل صحيح في كل مرة ، فلن يتوقف القطار أبدًا. إذا كنت تخمن بشكل خاطئ كثيرًا ، فسيقضي القطار الكثير من الوقت في التوقف والنسخ الاحتياطي وإعادة التشغيل.
ضع في اعتبارك عبارة if: على مستوى المعالج ، إنها تعليمات فرع:
أنت معالج وترى فرعًا. ليس لديك فكرة عن الطريقة التي ستسير بها الأمور. ماذا تفعل؟ أنت توقف التنفيذ وتنتظر حتى تكتمل التعليمات السابقة. ثم تواصل السير على الطريق الصحيح.
المعالجات الحديثة معقدة ولها خطوط أنابيب طويلة. لذلك يستغرقون إلى الأبد "الإحماء" و "الإبطاء".
هل هناك طريقة أفضل؟ تخمن في أي اتجاه سيذهب الفرع!
إذا خمنت بشكل صحيح ، فستستمر في التنفيذ.
إذا كنت خمنت بشكل خاطئ ، فأنت بحاجة إلى مسح خط الأنابيب والعودة إلى الفرع. ثم يمكنك إعادة تشغيل المسار الآخر.
إذا كنت تخمن بشكل صحيح في كل مرة ، فلن يتوقف الإعدام أبدًا. إذا كنت تخمن بشكل خاطئ كثيرًا ، فإنك تقضي الكثير من الوقت في المماطلة والتراجع وإعادة التشغيل.
هذا هو توقع الفرع. أعترف أنه ليس أفضل تشبيه لأن القطار يمكنه فقط الإشارة إلى الاتجاه بعلم. لكن في أجهزة الكمبيوتر ، لا يعرف المعالج الاتجاه الذي سيتجه إليه الفرع حتى اللحظة الأخيرة.
إذن ، كيف يمكنك تخمين استراتيجي لتقليل عدد المرات التي يجب أن يتراجع فيها القطار وينزل في المسار الآخر؟ أنت تنظر إلى التاريخ الماضي! إذا غادر القطار في 99٪ من الوقت ، فأنت تعتقد أنه غادر. إذا تم التناوب ، فأنت تقوم بالتناوب بين تخميناتك. إذا سارت في اتجاه واحد كل ثلاث مرات ، فستخمن نفس الشيء ...
بمعنى آخر ، تحاول تحديد نمط واتباعه. هذه هي الطريقة التي تعمل بها متنبئات الفروع بشكل أو بآخر.
معظم التطبيقات لها فروع حسنة التصرف. لذا فإن المتنبئين الحديثين بالفروع سيحققون عادةً معدلات إصابة> 90٪ ولكن عند مواجهة فروع لا يمكن التنبؤ بها مع عدم وجود أنماط يمكن التعرف عليها ، فإن تنبؤات الفروع تكون عديمة الفائدة تقريبًا.
قراءة إضافية: مقال "توقع الفرع" على ويكيبيديا.
كما تم التلميح أعلاه ، فإن الجاني هو عبارة if:
إذا (البيانات [ج]> = 128)
المجموع + = البيانات [ج] ؛
لاحظ أن البيانات موزعة بالتساوي بين 0 و 255. عند فرز البيانات ، لن يدخل النصف الأول تقريبًا من التكرارات عبارة if. بعد ذلك ، سيدخلون جميعًا عبارة if.
يعد هذا أمرًا وديًا جدًا لمتنبئ الفرع نظرًا لأن الفرع يسير في نفس الاتجاه على التوالي عدة مرات. حتى عداد التشبع البسيط سيتنبأ بشكل صحيح بالفرع باستثناء التكرارات القليلة بعد أن يغير الاتجاه.
التصور السريع:
T = الفرع المأخوذ
N = الفرع لم يؤخذ
البيانات [] = 0 ، 1 ، 2 ، 3 ، 4 ، ... 126 ، 127 ، 128 ، 129 ، 130 ، ... 250 ، 251 ، 252 ، ...
الفرع = N N N N N ... N N T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTT ... TTTTTTTTTT (من السهل التنبؤ بها)
ومع ذلك ، عندما تكون البيانات عشوائية تمامًا ، يصبح متنبئ الفرع عديم الفائدة ، لأنه لا يمكنه التنبؤ بالبيانات العشوائية. وبالتالي من المحتمل أن يكون هناك حوالي 50٪ خطأ في التنبؤ (ليس أفضل من التخمين العشوائي).
البيانات [] = 226 ، 185 ، 125 ، 158 ، 198 ، 144 ، 217 ، 79 ، 202 ، 118 ، 14 ، 150 ، 177 ، 182 ، 133 ، ...
الفرع = T ، T ، N ، T ، T ، T ، T ، N ، T ، N ، N ، T ، T ، T ، N ...
= TTNTTTTNTNNTTTN ... (عشوائي تمامًا - يصعب التنبؤ به)
إذن ما الذي يمكن عمله؟
إذا كان المترجم غير قادر على تحسين الفرع إلى خطوة شرطية ، يمكنك تجربة بعض الاختراقات إذا كنت على استعداد للتضحية بقابلية القراءة من أجل الأداء.
يحل محل:
إذا (البيانات [ج]> = 128)
المجموع + = البيانات [ج] ؛
مع:
int t = (data [c] - 128) >> 31 ؛
sum + = ~ t & data [c] ؛
هذا يلغي الفرع ويستبدله ببعض العمليات الأحادية.
(لاحظ أن هذا الاختراق لا يكافئ تمامًا جملة if الأصلية. ولكن في هذه الحالة ، يكون صالحًا لجميع قيم إدخال البيانات [].)
المعايير: Core i7 920 @ 3.5 GHz
C ++ - Visual Studio 2010 - إصدار x64
// فرع - عشوائي
الثواني = 11.777
// فرع - مرتبة
عدد الثواني = 2.352
// بدون فروع - عشوائي
ثواني = 2.564
// بدون فروع - مرتبة
ثواني = 2.587
جافا - NetBeans 7.1.1 JDK 7 - x64
// فرع - عشوائي
عدد الثواني = 10.93293813
// فرع - مرتبة
ثواني = 5.643797077
// بدون فروع -عشوائي
عدد الثواني = 3.113581453
// بدون فروع - مرتبة
عدد الثواني = 3.186068823
ملاحظات:
مع الفرع: هناك فرق كبير بين البيانات المصنفة وغير المصنفة.
مع Hack: لا يوجد فرق بين البيانات المصنفة وغير المصنفة.
في حالة C ++ ، يكون الاختراق في الواقع أبطأ من الفرع عندما يتم فرز البيانات.
تتمثل القاعدة العامة في تجنب التفرع المعتمد على البيانات في الحلقات الحرجة (كما في هذا المثال).
تحديث:
GCC 4.6.1 مع -O3 أو -ftree-vectorize على x64 قادر على إنشاء حركة مشروطة. لذلك لا يوجد فرق بين البيانات المصنفة وغير المصنفة - فكلاهما سريع.
(أو سريعًا إلى حد ما: بالنسبة للحالة التي تم فرزها بالفعل ، يمكن أن يكون cmov أبطأ خاصةً إذا كان مجلس التعاون الخليجي يضعه على المسار الحرج بدلاً من مجرد الإضافة ، خاصةً على Intel قبل Broadwell حيث يحتوي cmov على زمن انتقال لدورتين: علامة تحسين مجلس التعاون الخليجي -O3 تجعل الكود أبطأ من -O2)
يتعذر على VC ++ 2010 إنشاء تحركات شرطية لهذا الفرع حتى تحت / Ox.
يقوم مترجم Intel C ++ (ICC) 11 بشيء خارق. إنه يبدل الحلقتين ، وبالتالي يرفع الفرع غير المتوقع إلى الحلقة الخارجية. لذلك فهي ليست محصنة ضد سوء التوقع فحسب ، بل إنها أسرع بمرتين مما يمكن أن يولده VC ++ و GCC! بعبارة أخرى ، استفادت غرفة التجارة الدولية من حلقة الاختبار لهزيمة المعيار ...
إذا أعطيت برنامج التحويل البرمجي Intel الشفرة غير المتفرعة ، فسيؤدي ذلك إلى تحويله إلى الاتجاه الصحيح ... ويكون بنفس سرعة الفرع (مع تبادل الحلقة).
يوضح هذا أنه حتى المجمعين الحديثين الناضجين يمكن أن يختلفوا بشكل كبير في قدرتهم على تحسين الكود ...
|
توقع الفرع.
مع مصفوفة مرتبة ، تكون بيانات الشرط [c]> = 128 خاطئة أولاً لسلسلة من القيم ، ثم تصبح صحيحة لجميع القيم اللاحقة. من السهل التنبؤ. باستخدام مصفوفة لم يتم فرزها ، تقوم بدفع تكلفة التفريع.
|
السبب في تحسن الأداء بشكل كبير عند فرز البيانات هو إزالة عقوبة توقع الفرع ، كما هو موضح بشكل جميل في إجابة Mysticial.
الآن ، إذا نظرنا إلى الكود
إذا (البيانات [ج]> = 128)
المجموع + = البيانات [ج] ؛
يمكننا أن نجد أن معنى هذا بالتحديد إذا ... وإلا ... الفرع هو إضافة شيء ما عند استيفاء شرط. يمكن تحويل هذا النوع من الفروع بسهولة إلى عبارة حركة مشروطة ، والتي سيتم تجميعها في تعليمات حركة مشروطة: cmovl ، في نظام x86. يتم إزالة الفرع وبالتالي عقوبة توقع الفرع المحتملة.
في لغة C ، هكذا C ++ ، العبارة ، التي ستجمع مباشرة (بدون أي تحسين) في تعليمات الحركة الشرطية في x86 ، هل المشغل الثلاثي ...؟ ...: .... لذلك نعيد كتابة العبارة أعلاه إلى أخرى مكافئة:
المجموع + = البيانات [ج]> = 128؟ البيانات [ج]: 0 ؛
مع الحفاظ على قابلية القراءة ، يمكننا التحقق من عامل التسريع.
في Intel Core i7-2600K @ 3.4 GHz و Visual Studio 2010 Release Mode ، يكون المعيار (تنسيق منسوخ من Mysticial):
إلى x86
// فرع - عشوائي
الثواني = 8.885
// فرع - مرتبة
ثواني = 1.528
// بدون فروع - عشوائي
ثواني = 3.716
// بدون فروع - مرتبة
ثواني = 3.71
إلى x64
// فرع - عشوائي
الثواني = 11.302
// فرع - مرتبة
ثواني = 1.830
// بدون فروع - عشوائي
عدد الثواني = 2.736
// بدون فروع - مرتبة
ثواني = 2.737
كانت النتيجة قوية في اختبارات متعددة. نحصل على تسريع كبير عندما تكون النتيجة الفرعية غير متوقعة ، لكننا نعاني قليلاً عندما تكون متوقعة. في الواقع ، عند استخدام حركة شرطية ، يكون الأداء هو نفسه بغض النظر عن نمط البيانات.
الآن دعونا ننظر عن كثب من خلال التحقق من تجميع x86 الذي قاموا بإنشائه. للتبسيط ، نستخدم وظيفتين max1 و max2.
يستخدم max1 الفرع الشرطي إذا ... آخر ...:
int max1 (int a، int b) {
إذا (أ> ب)
عودة
آخر
العودة ب ؛
}
max2 يستخدم عامل التشغيل الثلاثي ...؟ ...: ...:
int max2 (int a، int b) {
العودة أ> ب؟ أ: ب ؛
}
على جهاز x86-64 ، ينشئ GCC -S التجميع أدناه.
: ماكس 1
movl٪ edi ، -4 (٪ rbp)
movl٪ esi ، -8 (٪ rbp)
movl -4 (٪ rbp) ،٪ eax
cmpl -8 (٪ rbp) ،٪ eax
jle .L2
movl -4 (٪ rbp) ،٪ eax
movl٪ eax ، -12 (٪ rbp)
جمب
.L2:
movl -8 (٪ rbp) ،٪ eax
movl٪ eax ، -12 (٪ rbp)
.L4:
movl -12 (٪ rbp) ،٪ eax
غادر
متقاعد
: ماكس 2
movl٪ edi ، -4 (٪ rbp)
movl٪ esi ، -8 (٪ rbp)
movl -4 (٪ rbp) ،٪ eax
cmpl٪ eax ، -8 (٪ rbp)
cmovge -8 (٪ rbp) ،٪ eax
غادر
متقاعد
يستخدم max2 رمزًا أقل بكثير بسبب استخدام التعليمات cmovge. لكن المكسب الحقيقي هو أن max2 لا يتضمن قفزات فرعية ، jmp ، والتي سيكون لها عقوبة أداء كبيرة إذا كانت النتيجة المتوقعة غير صحيحة.
فلماذا تؤدي الحركة الشرطية أداءً أفضل؟
في معالج x86 النموذجي ، ينقسم تنفيذ التعليمات إلى عدة مراحل. تقريبًا ، لدينا أجهزة مختلفة للتعامل مع المراحل المختلفة. لذلك لا يتعين علينا انتظار تعليمات واحدة حتى تنتهي لبدء واحدة جديدة. هذا يسمى خط الأنابيب.
في حالة الفرع ، يتم تحديد التعليمات التالية من خلال التعليمات السابقة ، لذلك لا يمكننا القيام بخط الأنابيب. علينا إما أن ننتظر أو نتوقع.
في حالة النقل الشرطي ،تنقسم تعليمات النقل الشرطي للتنفيذ إلى عدة مراحل ، ولكن المراحل السابقة مثل Fetch و Decode لا تعتمد على نتيجة التعليمات السابقة ؛ فقط المراحل الأخيرة تحتاج إلى النتيجة. وبالتالي ، فإننا ننتظر جزءًا بسيطًا من وقت تنفيذ أحد التعليمات. هذا هو السبب في أن إصدار الحركة الشرطية يكون أبطأ من الفرع عندما يكون التنبؤ سهلاً.
كتاب أنظمة الكمبيوتر: منظور مبرمج ، الطبعة الثانية يشرح هذا بالتفصيل. يمكنك التحقق من القسم 3.6.6 للحصول على إرشادات النقل الشرطي ، والفصل 4 بأكمله لهندسة المعالج ، والقسم 5.11.2 للحصول على معاملة خاصة لعقوبات التنبؤ والتنبؤ الخاطئ.
في بعض الأحيان ، يمكن لبعض برامج التحويل البرمجي الحديثة تحسين الكود الخاص بنا للتجميع بأداء أفضل ، وأحيانًا لا تستطيع بعض المجمعين (الكود المعني يستخدم مترجم Visual Studio الأصلي). إن معرفة فرق الأداء بين الفرع والحركة الشرطية عندما لا يمكن التنبؤ بها يمكن أن يساعدنا في كتابة التعليمات البرمجية بأداء أفضل عندما يصبح السيناريو معقدًا للغاية بحيث لا يستطيع المترجم تحسينها تلقائيًا.
|
إذا كنت مهتمًا بالمزيد من التحسينات التي يمكن إجراؤها على هذا الرمز ، ففكر في هذا:
بدءًا من الحلقة الأصلية:
لـ (بدون توقيع i = 0 ؛ i <100000 ؛ ++ i)
{
لـ (بدون علامة j = 0 ؛ j  = 128)
مجموع + = بيانات [ي] ؛
}
}
من خلال تبادل الحلقة ، يمكننا تغيير هذه الحلقة بأمان إلى:
لـ (بدون علامة j = 0 ؛ j  = 128)
مجموع + = بيانات [ي] ؛
}
}
بعد ذلك ، يمكنك أن ترى أن شرط if يكون ثابتًا طوال تنفيذ حلقة i ، لذا يمكنك رفع if للخارج:
لـ (بدون علامة j = 0 ؛ j  = 128)
{
لـ (بدون توقيع i = 0 ؛ i <100000 ؛ ++ i)
{
sum + = البيانات [j] ؛
}
}
}
بعد ذلك ، ترى أنه يمكن طي الحلقة الداخلية في تعبير واحد ، بافتراض أن نموذج النقطة العائمة يسمح بذلك (/ fp: يتم طرح سريع ، على سبيل المثال)
لـ (بدون علامة j = 0 ؛ j  = 128)
{
sum + = البيانات [j] * 100000 ؛
}
}
هذا هو 100000 مرة أسرع من ذي قبل.
|
لا شك أن البعض منا سيكون مهتمًا بطرق تحديد الكود الذي يمثل مشكلة بالنسبة لمتنبئ فرع وحدة المعالجة المركزية. تحتوي ذاكرة التخزين المؤقت لأداة Valgrind على محاكي توقع فرعي ، يتم تمكينه باستخدام العلامة --branch-sim = yes. باستخدام الأمثلة في هذا السؤال ، مع تقليل عدد الحلقات الخارجية إلى 10000 وتجميعها باستخدام g ++ ، يعطي النتائج التالية:
مرتبة:
== 32551 == الفروع: 656،645،130 (656،609،208 Cond + 35،922 ind)
== 32551 == التكهنات: 169،556 (169،095 كوند + 461 ind)
== 32551 == معدل الخطأ: 0.0٪ (0.0٪ + 1.2٪)
غير مصنف:
== 32555 == الفروع: 655،996،082 (655،960،160 كوند + 35،922 إند)
== 32555 == التكهنات الخاطئة: 164،073،152 (164،072،692 cond + 460 ind)
== 32555 == معدل الخطأ: 25.0٪ (25.0٪ + 1.2٪)
التنقيب في الإخراج سطريًا بسطر الناتج عن cg_annotate نرى الحلقة المعنية:
مرتبة:
قبل الميلاد Bcm ثنائية بيم
10،001 4 0 0 لـ (بدون توقيع i = 0 ؛ i <10000 ؛ ++ i)
. . . . {
. . . . // الحلقة الأولية
327،690،000 10،016 0 0 لـ (بدون إشارة c = 0 ؛ c  = 128)
0 0 0 0 sum + = البيانات [c] ؛
. . . . }
. . . . }
غير مصنف:
قبل الميلاد Bcm ثنائية بيم
10،001 4 0 0 لـ (بدون توقيع i = 0 ؛ i <10000 ؛ ++ i)
. . . . {
. . . . // الحلقة الأولية
327،690،000 10،038 0 0 لـ (بدون إشارة c = 0 ؛ c  = 128)
0 0 0 0 sum + = البيانات [c] ؛
. . . . }
. . . . }
يتيح لك هذا التعرف بسهولة على الخط الإشكالي - في الإصدار غير الفرز ، يتسبب سطر if (البيانات [c]> = 128) في إحداث 164،050،007 فرعًا شرطيًا خاطئًا (Bcm) ضمن نموذج توقع الفروع الخاص بـ cachegrind ، في حين أنه يتسبب فقط في 10.006 في الإصدار المصنف .
بدلاً من ذلك ، في Linux ، يمكنك استخدام النظام الفرعي لعدادات الأداء لإنجاز نفس المهمة ، ولكن مع الأداء الأصلي باستخدام عدادات وحدة المعالجة المركزية.
إحصائيات الأداء ./sumtest_sorted
مرتبة:
إحصائيات عداد الأداء لـ "./sumtest_sorted":
11808.095776 ساعة مهمة # 0.998 وحدات المعالجة المركزية المستخدمة
1،062 مفتاح تبديل سياق # 0.090 كلفن / ثانية
14 تهجير وحدة المعالجة المركزية # 0.001 ك / ثانية
337 أخطاء صفحة # 0.029 ك / ثانية
26،487،882،764 دورة # 2.243 جيجاهرتز
41،025،654،322 تعليمات # 1.55 إدخالًا لكل دورة
6،558،871،379 فرع # 555.455 م / ثانية
567204 فشل فرع # 0.01٪ من جميع الفروع
11.827228330 ثانية الوقت المنقضي
غير مصنف:
أداءإحصائيات مضادة لـ "./sumtest_unsorted":
تم استخدام 28877.954344 ساعة المهام # 0.998 وحدات المعالجة المركزية
2،584 تبديل سياق # 0.089 ك / ثانية
18 تهجير وحدة المعالجة المركزية # 0.001 ك / ثانية
335 أخطاء صفحة # 0.012 ك / ثانية
65،076،127،595 دورة # 2.253 جيجاهرتز
41،032،528،741 تعليمات # 0.63 إدخالًا لكل دورة
6،560،579،013 فرع # 227.183 م / ثانية
1،646،394،749 فشل فرع # 25.10٪ من جميع الفروع
انقضى الوقت 28.935500947 ثانية
يمكنه أيضًا إجراء شرح توضيحي لكود المصدر مع التفكيك.
سجل الأداء -e- الفروع يخطئ ./sumtest_unsorted
أداء التعليق التوضيحي -d sumtest_unsorted
في المئة | كود المصدر وتفكيك sumtest_unsorted
------------------------------------------------
...
: sum + = data [c]؛
0.00: 400a1a: mov -0x14 (٪ rbp) ،٪ eax
39.97: 400a1d: mov٪ eax،٪ eax
5.31: 400a1f: mov -0x20040 (٪ rbp،٪ rax، 4)،٪ eax
4.60: 400a26: cltq
0.00: 400a28: إضافة٪ rax ، -0x30 (٪ rbp)
...
انظر البرنامج التعليمي للأداء لمزيد من التفاصيل.
|
لقد قرأت للتو هذا السؤال وإجاباته ، وأشعر أن الإجابة مفقودة.
من الطرق الشائعة للتخلص من تنبؤات الفروع التي وجدت أنها تعمل بشكل جيد في اللغات المدارة هي البحث في الجدول بدلاً من استخدام فرع (على الرغم من أنني لم أختبره في هذه الحالة).
يعمل هذا النهج بشكل عام إذا:
إنها طاولة صغيرة ومن المحتمل أن تكون مخزنة مؤقتًا في المعالج ، و
أنت تقوم بتشغيل الأشياء في حلقة ضيقة تمامًا و / أو يمكن للمعالج تحميل البيانات مسبقًا.
الخلفية ولماذا
من منظور المعالج ، ذاكرتك بطيئة. للتعويض عن الاختلاف في السرعة ، تم تضمين اثنين من ذاكرات التخزين المؤقت في المعالج (ذاكرة التخزين المؤقت L1 / L2). لذا تخيل أنك تقوم بحساباتك الجيدة واكتشف أنك بحاجة إلى جزء من الذاكرة. سيحصل المعالج على عملية "التحميل" الخاصة به ويقوم بتحميل جزء من الذاكرة في ذاكرة التخزين المؤقت - ثم يستخدم ذاكرة التخزين المؤقت لإجراء باقي العمليات الحسابية. لأن الذاكرة بطيئة نسبيًا ، سيؤدي هذا "التحميل" إلى إبطاء برنامجك.
مثل توقع الفروع ، تم تحسين هذا في معالجات Pentium: يتوقع المعالج أنه يحتاج إلى تحميل جزء من البيانات ويحاول تحميل ذلك في ذاكرة التخزين المؤقت قبل أن تصل العملية فعليًا إلى ذاكرة التخزين المؤقت. كما رأينا بالفعل ، أحيانًا ما يكون التنبؤ بالفروع خاطئًا بشكل فظيع - في أسوأ السيناريوهات ، تحتاج إلى العودة والانتظار فعليًا لتحميل الذاكرة ، والذي سيستغرق إلى الأبد (بمعنى آخر: فشل توقع الفرع أمر سيء ، ذاكرة التحميل بعد فشل توقع الفرع أمر مروع!).
لحسن الحظ بالنسبة لنا ، إذا كان نمط الوصول إلى الذاكرة متوقعًا ، فسيقوم المعالج بتحميله في ذاكرة التخزين المؤقت السريعة وكل شيء على ما يرام.
أول شيء يجب أن نعرفه هو ما هو الصغير؟ في حين أن الأصغر هو الأفضل بشكل عام ، فإن القاعدة الأساسية هي الالتزام بجداول البحث التي يكون حجمها <= 4096 بايت. كحد أعلى: إذا كان جدول البحث أكبر من 64 كيلو بايت ، فمن المحتمل أن يكون من المفيد إعادة النظر فيه.
بناء طاولة
لذلك اكتشفنا أنه يمكننا إنشاء طاولة صغيرة. الشيء التالي الذي يجب فعله هو الحصول على وظيفة بحث في مكانها. عادةً ما تكون وظائف البحث وظائف صغيرة تستخدم عمليتين أساسيتين من عمليات الأعداد الصحيحة (و ، أو ، xor ، تحول ، إضافة ، حذف ، وربما الضرب). أنت تريد أن تتم ترجمة مدخلاتك من خلال وظيفة البحث إلى نوع من "المفتاح الفريد" في جدولك ، والذي يمنحك بعد ذلك ببساطة الإجابة عن كل العمل الذي تريده أن يقوم به.
في هذه الحالة:> = 128 يعني أنه يمكننا الاحتفاظ بالقيمة ، يعني <128 أننا نتخلص منها. أسهل طريقة للقيام بذلك هي استخدام "AND": إذا احتفظنا بها ، فإننا مع 7FFFFFFF ؛ إذا أردنا التخلص منه ، فنحن مع 0. لاحظ أيضًا أن 128 هي قوة 2 - لذلك يمكننا المضي قدمًا وإنشاء جدول من 32768/128 من الأعداد الصحيحة وملئه بصفر واحد والكثير من 7FFFFFFFF ل.
اللغات المدارة
قد تتساءل عن سبب نجاح ذلك في اللغات المدارة. بعد كل شيء ، تتحقق اللغات المدارة من حدود المصفوفات بفرع للتأكد من أنك لا تخطئ ...
حسنًا ، ليس بالضبط ... :-)
كان هناك بعض العمل على إلغاء هذا الفرع للغات المدارة. فمثلا:
لـ (int i = 0 ؛ i  = 128)؟ ج: 0 ؛
}
// اختبار
DateTime startTime = System.DateTime.Now ،
مجموع طويل = 0 ؛
لـ (int i = 0 ؛ i <100000 ؛ ++ i)
{
// الحلقة الأساسية
لـ (int j = 0 ؛ j  = 128. وهذا يعني أنه يمكننا بسهولة استخراج بت واحد يخبرنا ما إذا كنا نريد قيمة أم لا: عن طريق التحويل البيانات إلى 7 بتات اليمنى ، يتبقى لنا 0 بت أو 1 بت ، ونريد فقط إضافة القيمة عندما يكون لدينا 1 بت. دعنا نسمي هذا الجزء "بت القرار".
باستخدام القيمة 0/1 لبت القرار كمؤشر في مصفوفة ، يمكننا إنشاء رمز يكون سريعًا بنفس القدر سواء تم فرز البيانات أم لا. سيضيف الكود الخاص بنا دائمًا قيمة ، ولكن عندما يكون بت القرار 0 ، سنضيف القيمة في مكان ما لا نهتم به. ها هو الكود:
// اختبار
clock_t start = الساعة () ؛
طويل [] = {0 ، 0} ؛
مبلغ طويل
لـ (بدون توقيع i = 0 ؛ i <100000 ؛ ++ i)
{
// الحلقة الأساسية
لـ (بدون إشارة c = 0 ؛ c > 7) ؛
أ [ي] + = بيانات [ج] ؛
}
}
double elapsedTime = static_cast  (ساعة () - بداية) / CLOCKS_PER_SEC ؛
المجموع = أ [1] ؛
هذا الرمز يهدر نصف الإضافات ولكن لا يوجد به فشل في التنبؤ بالفرع. إنه أسرع بشكل كبير في البيانات العشوائية من الإصدار الذي يحتوي على عبارة if الفعلية.
ولكن في الاختبار الذي أجريته ، كان جدول البحث الصريح أسرع قليلاً من ذلك ، ربما لأن الفهرسة في جدول البحث كانت أسرع قليلاً من تحويل البت. يوضح هذا كيفية إعداد الكود الخاص بي واستخدامه لجدول البحث (يُطلق عليه اسم lut لـ "جدول البحث" في الكود). هذا هو كود C ++:
// أعلن ثم املأ جدول البحث
int lut [256] ؛
لـ (بدون توقيع c = 0 ؛ c <256 ؛ ++ c)
لوت [ج] = (ج> = 128)؟ ج: 0 ؛
// استخدم جدول البحث بعد بنائه
لـ (بدون توقيع i = 0 ؛ i <100000 ؛ ++ i)
{
// الحلقة الأساسية
لـ (بدون إشارة c = 0 ؛ c  قيمة)
عقدة = عقدة-> pLeft ؛
آخر
عقدة = عقدة-> ص ؛
ستقوم هذه المكتبة بعمل شيء مثل:
i = (x  value) ؛
عقدة = عقدة-> ارتباط [i] ؛
إليك رابط لهذا الرمز: Red Black Trees ، مرتبك إلى الأبد
|
في الحالة التي تم فرزها ، يمكنك القيام بعمل أفضل من الاعتماد على تنبؤ الفرع الناجح أو أي خدعة مقارنة بدون فروع: قم بإزالة الفرع تمامًا.
في الواقع ، يتم تقسيم المصفوفة في منطقة متجاورة تحتوي على بيانات <128 وأخرى تحتوي على بيانات> = 128. لذا يجب أن تجد نقطة التقسيم ببحث ثنائي النواة (باستخدام مقارنات Lg (arraySize) = 15) ، ثم قم بإجراء تجميع مباشر من هذه النقطة.
شيء من هذا القبيل (غير محدد)
int i = 0، j، k = arraySize ؛
بينما (أنا <ك)
{
ي = (أنا + ك) >> 1 ؛
إذا (البيانات [ي]> = 128)
ك = ي ؛
آخر
أنا = ي ؛
}
المجموع = 0 ؛
لـ (؛ i > 1 ؛
لـ (i = 0، k = arraySize؛ i  = 128؟ k: i) = j)
ي = (أنا + ك) >> 1 ؛
لـ (sum = 0 ؛ i  = 128)
/ \
/ \
/ \
خطأ صحيح
/ \
/ \
/ \
/ \
ب) المجموع + = البيانات [ج] ؛ ج) للحلقة أو الطباعة ().
بدون توقع الفرع ، سيحدث ما يلي:
لتنفيذ التعليمات B أو التعليمات C ، سيتعين على المعالج الانتظار حتى لا تصل التعليمات A إلى مرحلة EX في خط الأنابيب ، حيث يعتمد قرار الانتقال إلى التعليمات B أو التعليمات C على نتيجة التعليمات A. لذا فإن خط الأنابيب سيبدو هكذا.
عندما تكون الحالة صحيحة:
عندما يعود الشرط خطأ:
نتيجة انتظار نتيجة التعليمات A ، فإن إجمالي دورات وحدة المعالجة المركزية التي تم إنفاقها في الحالة المذكورة أعلاه (بدون توقع الفرع ؛ لكل من الصواب والخطأ) هو 7.
إذن ما هو توقع الفرع؟
سيحاول متنبئ الفرع تخمين الاتجاه الذي سيسلكه الفرع (بنية if-then-else) قبل أن يُعرف هذا على وجه اليقين. لن تنتظر التعليمات A للوصول إلى مرحلة EX من خط الأنابيب ، ولكنها ستخمن القرار وتنتقل إلى تلك التعليمات (B أو C في حالة مثالنا).
في حالة التخمين الصحيح ، يبدو خط الأنابيب كما يلي:
إذا تم الكشف لاحقًا أن التخمين كان خاطئًا ، فسيتم تجاهل التعليمات المنفذة جزئيًا ويبدأ خط الأنابيب من جديد مع الفرع الصحيح ، مما يؤدي إلى تأخير.
الوقت المهدر في حالة سوء التنبؤ في الفرع يساوي عدد المراحل في خط الأنابيب من مرحلة الجلب إلى مرحلة التنفيذ. تميل المعالجات الدقيقة الحديثة إلى امتلاك خطوط أنابيب طويلة جدًا بحيث يكون التأخير في التنبؤ الخاطئ بين 10 و 20 دورة على مدار الساعة. كلما زاد طول خط الأنابيب ، زادت الحاجة إلى توقع فرع جيد.
في كود OP ، في المرة الأولى التي لا يكون فيها متنبئ الفرع الشرطي أي معلومات لتأسيس التنبؤ ، لذلك في المرة الأولى سيختار بشكل عشوائي التعليمات التالية. لاحقًا في حلقة for ، يمكنها أن تبني التنبؤ على التاريخ.
بالنسبة لمصفوفة مرتبة بترتيب تصاعدي ، هناك ثلاثة احتمالات:
كل العناصر أقل من 128
جميع العناصر أكبر من 128
بعض عناصر البدء الجديدة أقل من 128 ، وبعد ذلك أصبحت أكبر من 128
لنفترض أن المتنبئ سيفترض دائمًا الفرع الحقيقي في الجولة الأولى.
لذلك في الحالة الأولى ، سيأخذ الأمر دائمًا في الحقيقةفرع منذ تاريخيا جميع التوقعات صحيحة.
في الحالة الثانية ، ستتنبأ في البداية بالخطأ ، ولكن بعد عدة تكرارات ، ستتوقع بشكل صحيح.
في الحالة الثالثة ، سوف يتنبأ مبدئيًا بشكل صحيح حتى تصبح العناصر أقل من 128. وبعد ذلك ستفشل لبعض الوقت وتصحح نفسها عندما ترى فشل توقع الفرع في التاريخ.
في كل هذه الحالات ، سيكون الفشل أقل من حيث العدد ، ونتيجة لذلك ، سيحتاج بضع مرات فقط إلى تجاهل التعليمات المنفذة جزئيًا والبدء من جديد بالفرع الصحيح ، مما يؤدي إلى عدد أقل من دورات وحدة المعالجة المركزية.
ولكن في حالة وجود مصفوفة عشوائية لم يتم فرزها ، سيحتاج التنبؤ إلى تجاهل التعليمات المنفذة جزئيًا والبدء من جديد بالفرع الصحيح في معظم الأوقات وينتج عنه المزيد من دورات وحدة المعالجة المركزية مقارنةً بالمصفوفة التي تم فرزها.
|
الجواب الرسمي سيكون من
Intel - تجنب تكلفة سوء التنبؤ في الفروع
إنتل - إعادة تنظيم الفروع والحلقة لمنع سوء التوقع
أوراق علمية - تنبؤ فرع هندسة الكمبيوتر
الكتب: J.L. Hennessy، D.A. باترسون: هندسة الكمبيوتر: نهج كمي
مقالات في المنشورات العلمية: T.Y. نعم ، Y.N. قدم بات الكثير من هذه التوقعات على أساس الفروع.
يمكنك أيضًا أن ترى من هذا الرسم التخطيطي الجميل سبب ارتباك متنبئ الفرع.
كل عنصر في الكود الأصلي هو قيمة عشوائية
البيانات [c] = std :: rand ()٪ 256 ؛
لذلك سوف يغير المتنبئ الجوانب مثل ضربة std :: rand ().
من ناحية أخرى ، بمجرد أن يتم فرزها ، سينتقل المتنبئ أولاً إلى حالة عدم أخذها بقوة وعندما تتغير القيم إلى القيمة العالية ، سيتغير المتنبئ خلال ثلاث دورات طوال الطريق من عدم أخذها بقوة إلى مأخوذة بقوة.
|
في نفس السطر (أعتقد أنه لم يتم إبراز هذا من خلال أي إجابة) ، من الجيد أن نذكر أنه في بعض الأحيان (خاصة في البرامج حيث يكون الأداء مهمًا - كما هو الحال في Linux kernel) يمكنك العثور على بعض عبارات if مثل ما يلي:
إذا (من المحتمل (كل شيء _ is_ok))
{
/* قم بعمل ما */
}
أو بالمثل:
إذا (غير محتمل (حالة_محتملة_جديدة))
{
/* قم بعمل ما */
}
كلا من المحتمل () وغير المحتمل () هما في الواقع وحدات ماكرو يتم تحديدها باستخدام شيء مثل توقع __builtin_expect الخاص بـ GCC لمساعدة المترجم على إدخال رمز التنبؤ لصالح الشرط مع مراعاة المعلومات المقدمة من قبل المستخدم. يدعم GCC إنشاءات أخرى يمكنها تغيير سلوك البرنامج قيد التشغيل أو إصدار تعليمات منخفضة المستوى مثل مسح ذاكرة التخزين المؤقت ، وما إلى ذلك. راجع هذه الوثائق التي تمر عبر بنى GCC المتاحة.
عادةً ما يتم العثور على هذا النوع من التحسينات بشكل أساسي في تطبيقات الوقت الفعلي الصعب أو الأنظمة المضمنة حيث يكون وقت التنفيذ أمرًا بالغ الأهمية. على سبيل المثال ، إذا كنت تتحقق من بعض حالات الخطأ التي تحدث فقط 1/10000000 مرة ، فلماذا لا تخبر المترجم بذلك؟ بهذه الطريقة ، افتراضيًا ، يفترض توقع الفرع أن الشرط خاطئ.
|
العمليات المنطقية المستخدمة بشكل متكرر في C ++ تنتج العديد من الفروع في البرنامج المترجم. إذا كانت هذه الفروع داخل حلقات ويصعب التنبؤ بها فإنها يمكن أن تبطئ التنفيذ بشكل كبير. يتم تخزين المتغيرات المنطقية على هيئة أعداد صحيحة 8 بت مع القيمة 0 للخطأ و 1 للصواب.
يتم تحديد المتغيرات المنطقية بشكل مفرط بمعنى أن جميع المشغلين الذين لديهم متغيرات منطقية كمدخلات يتحققون مما إذا كانت المدخلات لها أي قيمة أخرى غير 0 أو 1 ، لكن المشغلين الذين لديهم قيمة منطقية كمخرجات لا يمكن أن ينتجوا قيمة أخرى غير 0 أو 1. وهذا يجعل العمليات مع المتغيرات المنطقية كمدخلات أقل كفاءة من اللازم.
خذ بعين الاعتبار المثال:
منطقي أ ، ب ، ج ، د ؛
ج = أ && ب ؛
د = أ || ب؛
عادة ما يتم تنفيذ ذلك بواسطة المترجم بالطريقة التالية:
منطقي أ ، ب ، ج ، د ؛
إذا (أ! = 0) {
إذا (ب! = 0) {
ج = 1 ؛
}
آخر {
الانتقال إلى CFALSE ؛
}
}
آخر {
CFALSE:
ج = 0 ؛
}
إذا (أ == 0) {
إذا (ب == 0) {
د = 0 ؛
}
آخر {
الانتقال إلى DTRUE ؛
}
}
آخر {
DTRUE:
د = 1 ؛
}
هذا الرمز بعيد عن أن يكون الأمثل. قد تستغرق الفروع وقتًا طويلاً في حالة وجود أخطاء في التنبؤ. يمكن جعل العمليات المنطقية أكثر فاعلية إذا كان من المعروف على وجه اليقين أن المعاملات ليس لها قيم أخرى غير 0 و 1. السبب في عدم قيام المترجم بعمل مثل هذا الافتراض هو أن المتغيرات قد يكون لها قيم أخرى إذا كانت غير مهيأة أو تأتي من مصادر غير معروفة. يمكن تحسين الكود أعلاه إذا تمت تهيئة a و b لقيم صالحة أو إذا كانت تأتي من مشغلين ينتجون مخرجات منطقية. تبدو الشفرة المحسّنة كما يلي:
شار أ = 0 ، ب = 1 ، ج ، د ؛
ج = أ & ب ؛
د = أ | ب؛
يتم استخدام char بدلاً من منطقي من أجل إتاحة إمكانية استخدام عوامل تشغيل البت (& و |) بدلاً من العوامل المنطقية (&& و ||). عوامل تشغيل البت هي تعليمات فردية تستغرق دورة ساعة واحدة فقط. عامل التشغيل OR (|) يعمل حتى إذا كان لكل من a و b قيم أخرى غير 0 أو 1. قد يعطي عامل التشغيل AND (&) والعامل EXCLUSIVE OR (^) نتائج غير متسقة إذا كان للمعاملات قيم أخرى غير 0 و 1.
لا يمكن استخدام ~ لـ NOT. في حين أن،يمكنك عمل Boolean NOT على متغير معروف بأنه 0 أو 1 بواسطة XOR مع 1:
منطقي أ ، ب ؛
ب =! أ ؛
يمكن تحسينها من أجل:
شار أ = 0 ، ب ؛
ب = أ ^ 1 ؛
لا يمكن استبدال a && b بـ a & b إذا كان b تعبيرًا لا يجب تقييمه إذا كان a خطأ (&& لن يقيم b ، & will). وبالمثل ، أ || لا يمكن استبدال ب بـ | b إذا كان b تعبيرًا لا يجب تقييمه إذا كان a صحيحًا.
يكون استخدام عوامل تشغيل أحاديات أكثر فائدة إذا كانت المعاملات متغيرات مما لو كانت المعاملات مقارنات:
منطقي مزدوج x ، y ، z ؛
أ = x> y && z <5.0 ؛
هو الأمثل في معظم الحالات (إلا إذا كنت تتوقع أن تولد && التعبير العديد من أخطاء الفروع).
|
بالتأكيد!...
توقع الفرع يجعل المنطق يعمل بشكل أبطأ ، بسبب التبديل الذي يحدث في التعليمات البرمجية الخاصة بك! يبدو الأمر كما لو كنت تسير في شارع مستقيم أو شارع به الكثير من المنعطفات ، وبالتأكيد سيتم تنفيذ المسار المستقيم بشكل أسرع! ...
إذا تم فرز المصفوفة ، فإن الشرط الخاص بك خاطئ في الخطوة الأولى: البيانات [c]> = 128 ، ثم تصبح قيمة حقيقية لكامل الطريق حتى نهاية الشارع. هذه هي الطريقة التي تصل بها إلى نهاية المنطق بشكل أسرع. من ناحية أخرى ، باستخدام مصفوفة غير مرتبة ، تحتاج إلى الكثير من الدوران والمعالجة مما يجعل الكود الخاص بك يعمل بشكل أبطأ بالتأكيد ...
انظر إلى الصورة التي أنشأتها لك أدناه. أي شارع سينتهي بشكل أسرع؟
إذاً برمجيًا ، يتسبب التنبؤ بالفروع في أن تكون العملية أبطأ ...
في النهاية أيضًا ، من الجيد معرفة أن لدينا نوعين من تنبؤات الفروع التي سيؤثر كل منها على كودك بشكل مختلف:
1. ثابت
2. ديناميكي
يتم استخدام التنبؤ بالفرع الثابت بواسطة المعالج الدقيق في المرة الأولى
مصادفة فرع شرطي ، والتنبؤ بالفرع الديناميكي
تُستخدم لعمليات التنفيذ الناجحة لرمز الفرع الشرطي.
من أجل كتابة التعليمات البرمجية الخاصة بك بشكل فعال للاستفادة من هذه
القواعد ، عند كتابة بيانات if-else أو تبديل البيانات ، تحقق أكثر من ذلك
الحالات الشائعة أولاً والعمل تدريجياً وصولاً إلى الأقل شيوعًا.
لا تتطلب الحلقات بالضرورة أي ترتيب خاص لرمز
توقع فرع ثابت ، فقط حالة مكرر الحلقة
يستخدم عادة.
|
لقد تمت بالفعل الإجابة على هذا السؤال بشكل ممتاز عدة مرات. ما زلت أرغب في لفت انتباه المجموعة إلى تحليل آخر مثير للاهتمام.
في الآونة الأخيرة ، تم استخدام هذا المثال (تم تعديله بشكل طفيف جدًا) أيضًا كطريقة لتوضيح كيف يمكن وصف جزء من التعليمات البرمجية داخل البرنامج نفسه على Windows. على طول الطريق ، يوضح المؤلف أيضًا كيفية استخدام النتائج لتحديد المكان الذي يقضي فيه الرمز معظم وقته في كل من الحالة المصنفة وغير المصنفة. أخيرًا ، تُظهر القطعة أيضًا كيفية استخدام ميزة غير معروفة لـ HAL (طبقة تجريد الأجهزة) لتحديد مقدار التوقع الخاطئ للفرع في الحالة غير المفروزة.
الرابط هنا:
مظاهرة التنميط الذاتي
|
كما سبق ذكره من قبل الآخرين ، ما وراء اللغز هو متنبئ الفرع.
أنا لا أحاول إضافة شيء ولكن شرح المفهوم بطريقة أخرى.
توجد مقدمة موجزة عن الويكي تحتوي على نص ورسم تخطيطي.
يعجبني الشرح أدناه الذي يستخدم مخططًا لتوضيح متنبئ الفرع بشكل حدسي.
في هندسة الكمبيوتر ، يكون متنبئ الفرع هو ملف
الدائرة الرقمية التي تحاول تخمين اتجاه الفرع (على سبيل المثال
بنية if-then-else) قبل أن يُعرف هذا بالتأكيد. ال
الغرض من متنبئ الفرع هو تحسين التدفق في
خط أنابيب التعليمات. تلعب متنبئات الفروع دورًا مهمًا في
تحقيق أداء عالي الفعالية في العديد من خطوط الأنابيب الحديثة
معماريات المعالجات الدقيقة مثل x86.
عادةً ما يتم تنفيذ التفريع ثنائي الاتجاه بقفزة شرطية
تعليمات. القفزة الشرطية يمكن أن "لا تؤخذ" وتستمر
التنفيذ مع أول فرع من الكود الذي يليه على الفور
بعد القفزة المشروطة ، أو يمكن "نقلها" والقفز إلى أ
مكان مختلف في ذاكرة البرنامج حيث يوجد الفرع الثاني من الكود
مخزن. من غير المعروف على وجه اليقين ما إذا كانت القفزة المشروطة ستكون كذلك
تؤخذ أو لا تؤخذ حتى يتم حساب الشرط و
اجتازت القفزة الشرطية مرحلة التنفيذ في التعليمات
خط أنابيب (انظر الشكل 1).
استنادًا إلى السيناريو الموضح ، قمت بكتابة عرض توضيحي للرسوم المتحركة لإظهار كيفية تنفيذ التعليمات في خط أنابيب في مواقف مختلفة.
بدون توقع فرع.
بدون توقع الفرع ، سيتعين على المعالج الانتظار حتى ملف
اجتاز تعليمات القفز الشرطي مرحلة التنفيذ قبل
يمكن أن تدخل التعليمات التالية مرحلة الجلب في خط الأنابيب.
يحتوي المثال على ثلاثة تعليمات وأول واحد هو تعليمات القفز الشرطي. يمكن إدخال التعليمات الأخيرين في خط الأنابيب حتى يتم تنفيذ تعليمات القفز الشرطي.
سوف يستغرق الأمر 9 دورات على مدار الساعة لإكمال 3 تعليمات.
استخدم توقع الفرع ولا تأخذ قفزة مشروطة. لنفترض أن التنبؤ لا يأخذ ملفقفزة شرطية.
سوف يستغرق الأمر 7 دورات على مدار الساعة لإكمال 3 تعليمات.
استخدم توقع الفروع وخذ قفزة مشروطة. لنفترض أن التنبؤ لا يأخذ قفزة شرطية.
سوف يستغرق الأمر 9 دورات على مدار الساعة لإكمال 3 تعليمات.
الوقت الذي يضيع في حالة سوء التنبؤ فرع يساوي
عدد المراحل في خط الأنابيب من مرحلة الجلب إلى
مرحلة التنفيذ. تميل المعالجات الدقيقة الحديثة إلى أن تكون طويلة جدًا
خطوط الأنابيب بحيث يكون تأخير التنبؤ الخاطئ بين الساعة 10 و 20
دورات. نتيجة لذلك ، فإن جعل خط الأنابيب أطول يزيد من الحاجة إلى
متنبئ فرع أكثر تقدمًا.
كما ترى ، يبدو أنه ليس لدينا سبب لعدم استخدام متنبئ الفرع.
إنه عرض توضيحي بسيط للغاية يوضح الجزء الأساسي جدًا من Branch Predictor. إذا كانت هذه الصور المتحركة مزعجة ، فلا تتردد في إزالتها من الإجابة ويمكن للزوار أيضًا الحصول على شفرة المصدر التجريبية الحية من BranchPredictorDemo
|
مكاسب توقع الفروع!
من المهم أن نفهم أن سوء التنبؤ الفروع لا يبطئ البرامج. تكلفة التنبؤ الفائت هي تمامًا كما لو لم يكن توقع الفرع موجودًا وانتظرت تقييم التعبير لتحديد الكود المطلوب تشغيله (مزيد من التوضيح في الفقرة التالية).
إذا (تعبير)
{
// تشغيل 1
} آخر {
// تشغيل 2
}
عندما يكون هناك عبارة if-else \ switch ، فيجب تقييم التعبير لتحديد الكتلة التي يجب تنفيذها. في كود التجميع الذي تم إنشاؤه بواسطة المترجم ، يتم إدراج تعليمات الفرع الشرطي.
يمكن أن يتسبب تعليمات الفرع في أن يبدأ الكمبيوتر في تنفيذ تسلسل تعليمات مختلف وبالتالي ينحرف عن سلوكه الافتراضي لتنفيذ التعليمات بالترتيب (أي إذا كان التعبير خاطئًا ، يتخطى البرنامج رمز كتلة if) اعتمادًا على بعض الشروط ، هو تقييم التعبير في حالتنا.
ومع ذلك ، يحاول المترجم التنبؤ بالنتيجة قبل أن يتم تقييمها بالفعل. ستجلب التعليمات من كتلة if ، وإذا تبين أن التعبير صحيح ، فهذا رائع! لقد اكتسبنا الوقت الذي استغرقته لتقييمه وأحرزنا تقدمًا في الكود ؛ إذا لم يكن الأمر كذلك ، فنحن نقوم بتشغيل الكود الخاطئ ، ويتم مسح خط الأنابيب وتشغيل الكتلة الصحيحة.
التصور:
لنفترض أنك بحاجة إلى اختيار الطريق 1 أو الطريق 2. في انتظار أن يتحقق شريكك من الخريطة ، توقفت عند ## وانتظرت ، أو يمكنك فقط اختيار الطريق 1 وإذا كنت محظوظًا (الطريق 1 هو الطريق الصحيح) ، حسنًا ، لم يكن عليك الانتظار حتى يتحقق شريكك من الخريطة (لقد وفرت الوقت الذي كان سيستغرقه للتحقق من الخريطة) ، وإلا فسوف تعود إلى الوراء.
في حين أن تدفق خطوط الأنابيب سريع للغاية ، فإن القيام بهذه المقامرة في الوقت الحاضر يستحق كل هذا العناء. دائمًا ما يكون توقع البيانات المصنفة أو البيانات التي تتغير ببطء أسهل وأفضل من توقع التغييرات السريعة.
يا طريق 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
الطريق 2 \ --------------------------------
|
في ARM ، ليست هناك حاجة إلى فرع ، لأن كل تعليمات بها حقل شرط 4 بت ، والذي يختبر (بدون تكلفة) أيًا من 16 حالة مختلفة قد تنشأ في سجل حالة المعالج ، وإذا كان الشرط في التعليمات هو خطأ ، تم تخطي التعليمات. هذا يلغي الحاجة إلى الفروع القصيرة ، ولن يكون هناك توقع فرع لهذه الخوارزمية. لذلك ، ستعمل النسخة التي تم فرزها من هذه الخوارزمية بشكل أبطأ من الإصدار غير الفرز في ARM ، بسبب الحمل الزائد للفرز.
تبدو الحلقة الداخلية لهذه الخوارزمية كما يلي في لغة تجميع ARM:
MOV R0 ، # 0 // R0 = sum = 0
MOV R1 ، # 0 // R1 = ج = 0
ADR R2، data // R2 = addr of data array (ضع هذه التعليمات خارج الحلقة الخارجية)
.inner_loop // تسمية فرع الحلقة الداخلية
LDRB R3 ، [R2 ، R1] // R3 = بيانات [ج]
CMP R3 ، # 128 // قارن R3 بـ 128
ADDGE R0، R0، R3 // if R3> = 128 ، ثم جمع + = بيانات [c] - لا حاجة إلى فرع!
إضافة R1، R1، # 1 // c ++
CMP R1 ، #arraySize // قارن c بـ arraySize
BLT inner_loop // فرع إلى الحلقة الداخلية إذا كانت c  ()) ؛
لـ (بدون إشارة c = 0 ؛ c  = 128
sum = sum + data1 (j) ؛
النهاية
النهاية
النهاية
توك.
ExeTimeWithSorting = toc - tic ؛
نتائج رمز MATLAB أعلاه هي كما يلي:
أ: الوقت المنقضي (بدون الفرز) = 3479.880861 ثانية.
ب: الوقت المنقضي (بالفرز) = 2377.873098 ثانية.
نتائج كود C كما فيGManNickG أحصل عليها:
أ: الوقت المنقضي (بدون الفرز) = 19.8761 ثانية.
ب: الوقت المنقضي (مع الفرز) = 7.37778 ثانية.
بناءً على ذلك ، يبدو أن MATLAB أبطأ بنحو 175 مرة من تنفيذ C بدون فرز و 350 مرة أبطأ مع الفرز. وبعبارة أخرى ، فإن تأثير (توقع الفرع) هو 1.46x لتطبيق MATLAB و 2.7x لتطبيق C.
|
الافتراض من خلال الإجابات الأخرى بأن المرء يحتاج إلى فرز البيانات غير صحيح.
لا يقوم الكود التالي بفرز المصفوفة بأكملها ، ولكن فقط 200 عنصر منها ، وبالتالي يتم تشغيل الأسرع.
يؤدي فرز أقسام عنصر k فقط إلى إكمال المعالجة المسبقة في الوقت الخطي ، O (n) ، بدلاً من O (n.log (n)) الوقت اللازم لفرز الصفيف بأكمله.
# تضمين <الخوارزمية>
# تضمين 
# تضمين 
انت مين() {
بيانات int [32768] ؛ const int l = حجم البيانات / حجم البيانات [0] ؛
لـ (غير موقعة c = 0 ؛ c  = 128)
المجموع + = البيانات [ج] ؛
}
}
std :: cout << static_cast  (ساعة () - بداية) / CLOCKS_PER_SEC << std :: endl؛
std :: cout << "sum =" << sum << std :: endl؛
}
هذا أيضًا "يثبت" أنه لا علاقة له بأي مشكلة خوارزمية مثل ترتيب الفرز ، وهو بالفعل تنبؤ بالفرع.
|
إجابة Bjarne Stroustrup على هذا السؤال:
هذا يبدو وكأنه سؤال مقابلة. هل هذا صحيح؟ كيف تعرف؟ إنها فكرة سيئة أن تجيب على الأسئلة المتعلقة بالكفاءة دون إجراء بعض القياسات أولاً ، لذلك من المهم معرفة كيفية القياس.
لذلك ، حاولت باستخدام متجه مليون عدد صحيح وحصلت على:
تم فرزها بالفعل 32995 مللي ثانية
خلط 125944 مللي ثانية
تم فرزها بالفعل 18610 ميلي ثانية
خلط 133304 مللي ثانية
تم فرزها بالفعل 17942 مللي ثانية
خلط 107858 مللي ثانية
ركضت ذلك عدة مرات للتأكد. نعم ، هذه الظاهرة حقيقية. كان رمز المفتاح الخاص بي هو:
تشغيل باطل (ناقل  & v ، سلسلة const والتسمية)
{
auto t0 = system_clock :: now () ؛
فرز (v.begin () ، v.end ()) ؛
auto t1 = system_clock :: now () ؛
cout << التسمية
<< period_cast  (t1 - t0) .count ()
<< "مللي ثانية \ n"؛
}
باطل tst ()
{
المتجه  v (1'000'000) ؛
ذرة (v.begin () ، v.end () ، 0) ؛
تشغيل (v ، "تم فرزها بالفعل") ؛
std :: shuffle (v.begin ()، v.end ()، std :: mt19937 {std :: random_device {} ()}) ؛
تشغيل (v ، "خلط") ؛
}
هذه الظاهرة حقيقية على الأقل مع هذا المترجم والمكتبة القياسية وإعدادات المحسن. يمكن للتطبيقات المختلفة أن تعطي إجابات مختلفة. في الواقع ، أجرى شخص ما دراسة أكثر منهجية (سيجدها بحث سريع على الويب) وأظهرت معظم التطبيقات هذا التأثير.
أحد الأسباب هو توقع الفرع: العملية الرئيسية في خوارزمية الفرز هي "if (v [i]  = 128. وهذا يعني أنه يمكننا بسهولة استخراج بت واحد يخبرنا ما إذا كنا نريد قيمة أم لا: عن طريق التحويل البيانات إلى 7 بتات اليمنى ، يتبقى لنا 0 بت أو 1 بت ، ونريد فقط إضافة القيمة عندما يكون لدينا 1 بت. دعنا نسمي هذا الجزء "بت القرار".
باستخدام القيمة 0/1 لبت القرار كمؤشر في مصفوفة ، يمكننا إنشاء رمز يكون سريعًا بنفس القدر سواء تم فرز البيانات أم لا. سيضيف الكود الخاص بنا دائمًا قيمة ، ولكن عندما يكون بت القرار 0 ، سنضيف القيمة في مكان ما لا نهتم به. ها هو الكود:
// اختبار
clock_t start = الساعة () ؛
طويل [] = {0 ، 0} ؛
مبلغ طويل
لـ (بدون توقيع i = 0 ؛ i <100000 ؛ ++ i)
{
// الحلقة الأساسية
لـ (بدون إشارة c = 0 ؛ c > 7) ؛
أ [ي] + = بيانات [ج] ؛
}
}
double elapsedTime = بث ثابت <مزدوج> (الساعة () - البداية) / CLOCKS_PER_SEC ؛
المجموع = أ [1] ؛
هذا الرمز يهدر نصف الإضافات ولكن لا يوجد به فشل في التنبؤ بالفرع. إنه أسرع بشكل كبير في البيانات العشوائية من الإصدار الذي يحتوي على عبارة if الفعلية.
ولكن في الاختبار الذي أجريته ، كان جدول البحث الصريح أسرع قليلاً من ذلك ، ربما لأن الفهرسة في جدول البحث كانت أسرع قليلاً من تحويل البت. يوضح هذا كيفية إعداد الكود الخاص بي واستخدامه لجدول البحث (يُطلق عليه اسم lut لـ "جدول البحث" في الكود). هذا هو كود C ++:
// أعلن ثم املأ جدول البحث
int lut [256] ؛
لـ (بدون توقيع c = 0 ؛ c <256 ؛ ++ c)
لوت [ج] = (ج> = 128)؟ ج: 0 ؛
// استخدم جدول البحث بعد بنائه
لـ (بدون توقيع i = 0 ؛ i <100000 ؛ ++ i)
{
// الحلقة الأساسية
لـ (بدون إشارة c = 0 ؛ c  قيمة)
عقدة = عقدة-> pLeft ؛
آخر
عقدة = عقدة-> ص ؛
ستقوم هذه المكتبة بعمل شيء مثل:
i = (x  value) ؛
عقدة = عقدة-> ارتباط [i] ؛
إنه حل جيد وربما ينجح.
|
سؤال نشط للغاية. اكسب 10 سمعة للإجابة على هذا السؤال. تساعد متطلبات السمعة في حماية هذا السؤال من البريد العشوائي ونشاط عدم الإجابة.
ليس الجواب الذي تبحث عنه؟ تصفح الأسئلة الأخرى الموسومة بتحسين أداء جافا سي ++ ، توقع فرع أو اطرح سؤالك الخاص.